#include <iostream>
#define isSq 1									//0为线性存储，1为链式存储
#if isSq
	#include "sqlist.h"
	#define listType SqList
#else
	#include "llist.h"
	#define listType LList
#endif

using namespace std;

listType listMerge(listType &lista, listType &listb);
int main()
{
	listType lista, listb;
	int len;
	lista.ListInsert(1);
	lista.ListInsert(2);
	lista.ListInsert(3);
	lista.ListInsert(5);
	lista.ListInsert(8);
	lista.ListInsert(10);
	listb.ListInsert(1);
	listb.ListInsert(3);
	listb.ListInsert(6);
	listb.ListInsert(7);
	listb.ListInsert(10);
	cout << "The first list: ";					//输出两个线性表的内容
	len = lista.ListLength();
	for(int i = 1; i <= len; i++)
		cout << lista.GetElem(i) << " ";
	cout << endl << "The second list: ";
	len = listb.ListLength();
	for(int i = 1; i <= len; i++)
		cout << listb.GetElem(i) << " ";
	listType listc;
	listc = listMerge(lista, listb);			//合并两个线性表
	cout << endl << "The merged list: ";		//将合并后的线性表内容输出
	len = listc.ListLength();
	for(int i = 1; i <= len; i++)
		cout << listc.GetElem(i) << " ";
	cout << endl;
	return 0;
}

listType listMerge(listType &lista, listType &listb)
{
	listType fin;
	int lena, lenb, pa, pb;
	ElemType data, datb;
	lena = lista.ListLength();
	lenb = listb.ListLength();
	pa = pb = 1;
	while(pa <= lena && pb <= lenb)
	{
		data = lista.GetElem(pa);
		datb = listb.GetElem(pb);
		if(data < datb)
		{
			fin.ListInsert(data);
			pa++;
		}
		else if(data > datb)
		{
			fin.ListInsert(datb);
			pb++;
		}
		else
		{
			fin.ListInsert(data);
			pa++;
			pb++;
		}
	}
	if(pa <= lena)
		while(pa <= lena)
			fin.ListInsert(lista.GetElem(pa++));
	else
		while(pb <= lenb)
			fin.ListInsert(listb.GetElem(pb++));
	return fin;
}